{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子近似优化算法\n",
    "\n",
    "[![](https://gitee.com/mindspore/docs/raw/master/resource/_static/logo_source.png)](https://gitee.com/mindspore/docs/blob/master/docs/mindquantum/docs/source_zh_cn/quantum_approximate_optimization_algorithm.ipynb)\n",
    "\n",
    "## 概述\n",
    "\n",
    "量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是利用量子计算机来近似解决组合优化问题的量子算法，最早由Farhi等人于2014年提出。在本文档里，我们将利用QAOA算法来解决最大割问题（Max-Cut），来熟悉MindQuantum中量子线路的搭建和训练。\n",
    "\n",
    "> 本文档适用于CPU环境。\n",
    "> 你可以在这里找到完整的可运行的样例代码：<https://gitee.com/mindspore/mindquantum/blob/master/tutorials/source/quantum_approximate_optimization_algorithm.py>。\n",
    "\n",
    "## 环境准备\n",
    "\n",
    "本文档所需要的额外库：\n",
    "\n",
    "- networkx\n",
    "\n",
    "> `networkx`是创建、操作和研究复杂网络的结构、动态和功能库。可通过如下代码来进行安装。"
   ]
  },
  {
   "source": [
    "```bash\n",
    "pip3 install networkx\n",
    "```"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## Max-Cut问题描述\n",
    "\n",
    "Max-Cut问题是图论中的一个NP-complete问题，它需要将一个图中的顶点分成两部分，并使得两部分被切割的边最多。如下图（a），一个图由五个顶点构成，相互连接的边为```(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (0, 4)```。为了使得被切割的边最多，我们尝试通过（b）图的分割，将1、2、4分为一组，0、3分成另一组，因此可得到被切割的边有5条。后面我们将用穷举法验证这个解是否正确。当图中顶点较少时，我们可以在较短时间内通过穷举法找到最大的切割边数，但当图中顶点增多时，我们很难找到有效的经典算法来解决Max-Cut问题，因为这类NP-complete问题很有可能不存在多项式时间算法。但尽管精确解不容易得到，我们却可以想办法在多项式时间内找到问题的一个近似解，这就是近似优化算法。下面，我们介绍怎么将Max-Cut问题转化为一个哈密顿量的基态能量求解问题。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![max cut](https://gitee.com/mindspore/docs/raw/master/docs/mindquantum/docs/source_zh_cn/images/Max_Cut.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Max-Cut问题量子化\n",
    "\n",
    "这里我们将图中的每个顶点赋予一个量子比特，当顶点被分到左边时，我们将该顶点上的量子比特设置为$\\left|0\\right>$态，同理，右边为$\\left|1\\right>$态，当两个顶点被分到不同的集合中时，这两个顶点上的比特将处于不同的量子态。例如对于第0个顶点和第1个顶点，当其连线被切割时，两个顶点上的比特对应的量子态可以表示为$|01\\rangle$（顶点1：左，顶点0：右）或$|10\\rangle$（顶点1：右，顶点0：左）；若它们被分到同一边，则对应量子态为$|00\\rangle$或$|11\\rangle$。因此我们只要找到一个哈密顿量$H$使得：当有连线的两个顶点处于不同量子态时，哈密顿量的期望值为-1，即\n",
    "\n",
    "$$\n",
    "\\langle 01|H|01\\rangle=-1,\\quad \\langle 10|H|10\\rangle=-1\n",
    "$$\n",
    "\n",
    "而当有连线的顶点处于相同量子态时，哈密顿量的期望值为0，即\n",
    "\n",
    "$$\n",
    "\\langle 00|H|00\\rangle=0,\\quad \\langle 11|H|11\\rangle=0\n",
    "$$\n",
    "\n",
    "随后只要使哈密顿量的期望值最小化，就可以找到最大切割边数，以及此时对应的分组情况。之所以将不同量子态时的期望值设为-1，是因为在量子神经网络的训练中，Ansatz中的参数的梯度会一直下降，同时测量值也会一直减少，该训练方法就是以找到最小值为目标，这里我们用它来寻找哈密顿量的基态能量。此时，我们选择哈密顿量$H=(Z_1Z_0-1)/2$，这里$Z$为泡利$Z$算符。此时有：\n",
    "\n",
    "$$\n",
    "Z_1Z_0|00\\rangle=|00\\rangle,\\quad Z_1Z_0|11\\rangle=|11\\rangle, \\quad Z_1Z_0|01\\rangle=-|01\\rangle, \\quad Z_1Z_0|10\\rangle=-|10\\rangle\n",
    "$$\n",
    "\n",
    "因此当顶点被分到不同集合时：\n",
    "\n",
    "$$\n",
    "\\left<01\\right|H\\left|01\\right>=\\frac{1}{2}\\left<01\\right|Z_1Z_0\\left|01\\right>-\\frac{1}{2}=-1\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\left<10\\right|H\\left|10\\right>=\\frac{1}{2}\\left<10\\right|Z_1Z_0\\left|10\\right>-\\frac{1}{2}=-1\n",
    "$$\n",
    "\n",
    "而当顶点被分到同一集合中时，不难验证此时：\n",
    "\n",
    "$$\n",
    "\\left<00\\right|H\\left|00\\right>=\\frac{1}{2}\\left<00\\right|Z_1Z_0\\left|00\\right>-\\frac{1}{2}=0\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\left<11\\right|H\\left|11\\right>=\\frac{1}{2}\\left<11\\right|Z_1Z_0\\left|11\\right>-\\frac{1}{2}=0\n",
    "$$\n",
    "\n",
    "因此，我们只要对图中的每条边写出上述哈密顿量，然后将所有边求和，即可写出图对应的哈密顿量$H$，利用量子计算机求得$H$的基态能量与基态，我们就可以得到该图的Max-Cut切割方案与最大切割边数。我们记所有边的集合为$C$，所有边条数为$c$，则哈密顿量可写为：\n",
    "\n",
    "$$\n",
    "H=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n",
    "$$\n",
    "\n",
    "## 导入相关依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum.core import Circuit, Hamiltonian, UN, H, ZZ, RX, QubitOperator\n",
    "from mindquantum.framework import MQAnsatzOnlyLayer\n",
    "from mindquantum.simulator import Simulator\n",
    "import networkx as nx\n",
    "import mindspore.nn as nn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建所需求解的图\n",
    "\n",
    "通过`add_path`可在图中添加边。最后画出图的结构。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"446.4pt\" height=\"302.4pt\" viewBox=\"0 0 446.4 302.4\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2022-01-04T09:57:59.051559</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.5.0, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 302.4 \nL 446.4 302.4 \nL 446.4 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"LineCollection_1\">\n    <path d=\"M 84.096361 145.464691 \nL 44.687603 270.208264 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n    <path d=\"M 84.096361 145.464691 \nL 227.495925 32.191736 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n    <path d=\"M 84.096361 145.464691 \nL 246.000883 216.887273 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n    <path d=\"M 44.687603 270.208264 \nL 246.000883 216.887273 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n    <path d=\"M 246.000883 216.887273 \nL 401.712397 109.025692 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n    <path d=\"M 401.712397 109.025692 \nL 227.495925 32.191736 \n\" clip-path=\"url(#p3313d2dc63)\" style=\"fill: none; stroke: #000000\"/>\n   </g>\n   <g id=\"PathCollection_1\">\n    <defs>\n     <path id=\"m6c92e7439f\" d=\"M 0 8.660254 \nC 2.296726 8.660254 4.499694 7.747755 6.123724 6.123724 \nC 7.747755 4.499694 8.660254 2.296726 8.660254 0 \nC 8.660254 -2.296726 7.747755 -4.499694 6.123724 -6.123724 \nC 4.499694 -7.747755 2.296726 -8.660254 0 -8.660254 \nC -2.296726 -8.660254 -4.499694 -7.747755 -6.123724 -6.123724 \nC -7.747755 -4.499694 -8.660254 -2.296726 -8.660254 0 \nC -8.660254 2.296726 -7.747755 4.499694 -6.123724 6.123724 \nC -4.499694 7.747755 -2.296726 8.660254 0 8.660254 \nz\n\" style=\"stroke: #1f78b4\"/>\n    </defs>\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <use xlink:href=\"#m6c92e7439f\" x=\"84.096361\" y=\"145.464691\" style=\"fill: #1f78b4; stroke: #1f78b4\"/>\n     <use xlink:href=\"#m6c92e7439f\" x=\"44.687603\" y=\"270.208264\" style=\"fill: #1f78b4; stroke: #1f78b4\"/>\n     <use xlink:href=\"#m6c92e7439f\" x=\"246.000883\" y=\"216.887273\" style=\"fill: #1f78b4; stroke: #1f78b4\"/>\n     <use xlink:href=\"#m6c92e7439f\" x=\"401.712397\" y=\"109.025692\" style=\"fill: #1f78b4; stroke: #1f78b4\"/>\n     <use xlink:href=\"#m6c92e7439f\" x=\"227.495925\" y=\"32.191736\" style=\"fill: #1f78b4; stroke: #1f78b4\"/>\n    </g>\n   </g>\n   <g id=\"text_1\">\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <!-- 0 -->\n     <g transform=\"translate(79.921673 148.775941)scale(0.12 -0.12)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-30\" d=\"M 2944 2338 \nQ 2944 3213 2780 3570 \nQ 2616 3928 2228 3928 \nQ 1841 3928 1675 3570 \nQ 1509 3213 1509 2338 \nQ 1509 1453 1675 1090 \nQ 1841 728 2228 728 \nQ 2613 728 2778 1090 \nQ 2944 1453 2944 2338 \nz\nM 4147 2328 \nQ 4147 1169 3647 539 \nQ 3147 -91 2228 -91 \nQ 1306 -91 806 539 \nQ 306 1169 306 2328 \nQ 306 3491 806 4120 \nQ 1306 4750 2228 4750 \nQ 3147 4750 3647 4120 \nQ 4147 3491 4147 2328 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-30\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"text_2\">\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <!-- 1 -->\n     <g transform=\"translate(40.512916 273.519514)scale(0.12 -0.12)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-31\" d=\"M 750 831 \nL 1813 831 \nL 1813 3847 \nL 722 3622 \nL 722 4441 \nL 1806 4666 \nL 2950 4666 \nL 2950 831 \nL 4013 831 \nL 4013 0 \nL 750 0 \nL 750 831 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-31\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"text_3\">\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <!-- 2 -->\n     <g transform=\"translate(241.826195 220.198523)scale(0.12 -0.12)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-32\" d=\"M 1844 884 \nL 3897 884 \nL 3897 0 \nL 506 0 \nL 506 884 \nL 2209 2388 \nQ 2438 2594 2547 2791 \nQ 2656 2988 2656 3200 \nQ 2656 3528 2436 3728 \nQ 2216 3928 1850 3928 \nQ 1569 3928 1234 3808 \nQ 900 3688 519 3450 \nL 519 4475 \nQ 925 4609 1322 4679 \nQ 1719 4750 2100 4750 \nQ 2938 4750 3402 4381 \nQ 3866 4013 3866 3353 \nQ 3866 2972 3669 2642 \nQ 3472 2313 2841 1759 \nL 1844 884 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-32\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"text_4\">\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <!-- 3 -->\n     <g transform=\"translate(397.537709 112.336942)scale(0.12 -0.12)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-33\" d=\"M 2981 2516 \nQ 3453 2394 3698 2092 \nQ 3944 1791 3944 1325 \nQ 3944 631 3412 270 \nQ 2881 -91 1863 -91 \nQ 1503 -91 1142 -33 \nQ 781 25 428 141 \nL 428 1069 \nQ 766 900 1098 814 \nQ 1431 728 1753 728 \nQ 2231 728 2486 893 \nQ 2741 1059 2741 1369 \nQ 2741 1688 2480 1852 \nQ 2219 2016 1709 2016 \nL 1228 2016 \nL 1228 2791 \nL 1734 2791 \nQ 2188 2791 2409 2933 \nQ 2631 3075 2631 3366 \nQ 2631 3634 2415 3781 \nQ 2200 3928 1806 3928 \nQ 1516 3928 1219 3862 \nQ 922 3797 628 3669 \nL 628 4550 \nQ 984 4650 1334 4700 \nQ 1684 4750 2022 4750 \nQ 2931 4750 3382 4451 \nQ 3834 4153 3834 3553 \nQ 3834 3144 3618 2883 \nQ 3403 2622 2981 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-33\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"text_5\">\n    <g clip-path=\"url(#p3313d2dc63)\">\n     <!-- 4 -->\n     <g transform=\"translate(223.321237 35.502986)scale(0.12 -0.12)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-34\" d=\"M 2356 3675 \nL 1038 1722 \nL 2356 1722 \nL 2356 3675 \nz\nM 2156 4666 \nL 3494 4666 \nL 3494 1722 \nL 4159 1722 \nL 4159 850 \nL 3494 850 \nL 3494 0 \nL 2356 0 \nL 2356 850 \nL 288 850 \nL 288 1881 \nL 2156 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-34\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p3313d2dc63\">\n   <rect x=\"7.2\" y=\"7.2\" width=\"432\" height=\"288\"/>\n  </clipPath>\n </defs>\n</svg>\n",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8/fFQqAAAACXBIWXMAAAsTAAALEwEAmpwYAAA5L0lEQVR4nO3dd1iV9f8/8OdhKDhwK25FDdSUKYEjEE450sKVaFKRA0RRafkp26lp/vKAhqalJjgTBRVLVBBcIEMFB+AExVBxICDrjPv3h3m+kThA4D7j+biuz3UV53h46vWhp+/3fb/vl0QQBAFERER6wkDsAERERHWJxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHqFxUdERHrFSOwARPrsdlEZwlJykHGjAAWlCpiZGMHK3Azj7DugRaP6Yscj0kkSQRAEsUMQ6ZvUa/kIjr2IuPN5AIAyhUr9momRAQQArpat4OfSHdYdm4oTkkhHsfiI6tiGhCws+DMDpQolnvbTJ5EAJkaGmDfcCpOcutRZPiJdx61Oojr0sPTSUSJXPfO9ggCUyJVY8Gc6ALD8iGoIV3xEdST1Wj48f01AiVxZ6esPzsXh9q4lAIDGDm+iuXSa+jVTY0NsneaEvh2a1kVUIp3GuzqJ6khw7EWUKiovPUXBbdyNWgEYGFb6eqlCiRWxF2szHpHeYPER1YHbRWWIO59X6TU9QRBwZ89SGDZugQaW/Sv99YIAHMzMw52islpOSqT7WHxEdSAsJeeJrxUm7URpzjm0HPkxJIb1nvg+CYCwE0/+HCJ6Piw+ojqQcaOgwpGFR8rzsnAvbj2aDpqEem0snvoZpQoVMnILaysikd7gXZ1EdaCgVFHp14szjwFKBUqvnkbZtbMov3UFAFBy4TjuGdVDM9f3//M58tqOSqTzWHxEdcDM5Ak/aoIAQEDp5ZQKX1bcv4my6xmVfI5xLaQj0i8sPqI6YGVuhvpGNx7b7mw66B00HfSO+t9vR8rw4Ez0Y8cZAKCeAWBp3rhO8hLpMl7jI6oDY+07vPBnlMvlWDNvCrZs2QK5nFueRNXFA+xEdWRaaDL2n7sBAZIq/1qJBHi9ZxsMa5yDwMBAXL58GTNnzsTUqVPRrFmzWkhLpLu44iOqAwqFAqozf0FQlFfr15sYGWLG4O7w8PBAbGwsIiIicObMGVhYWGDGjBk4f/58DScm0l0sPqJadvv2bQwbNgzZJw7hf0MsYWpctR87U2MDzBtuVeFxZXZ2dggJCcHZs2fRrFkzDBw4ECNHjkRMTAy4iUP0dCw+olqUkpICBwcH2NvbY+/evfCV9sa84T1hamwIyTN2PCWSh8/onDe85xMfUN2uXTvMnz8fWVlZGDlyJGbOnAlbW1v8/vvvKCvjU16IKsNrfES1ZP369fjkk0+wcuVKjBkzpsJraTn5WBF7EQcz8yDBw8PpjzyaxzfYshX8XLtX6cHUKpUK+/btg0wmQ1paGqZPnw5fX1+0bt26Zn5TRDqAxUdUw8rLyxEQEIADBw4gPDwcvXr1euJ77xSVIexEDjJyC1FQKoeZiTGs2jbGWLsXn8B+9uxZBAUFYdu2bRgzZgzmzJmDl19++YU+k0gXsPiIatDff/+NsWPHonXr1li/fj2aNGkidiTk5eVh1apVWLFiBXr37o2AgAAMHToUBga80kH6icVHVEMOHz4MT09P+Pn54bPPPtO4YikrK8PWrVshk8lQWlqK2bNn491330WDBg3EjkZUp1h8RC9IEAT8/PPPmD9/PtavX4+hQ4eKHempBEFAXFwcZDIZjh07hqlTp2LGjBlo37692NGI6oRm/ZWUSMsUFxfjvffew5o1axAfH6/xpQcAEokErq6u2LlzJ+Lj41FYWIg+ffpg0qRJSE5OFjseUa1j8RFV05UrVzBgwAAolUocO3YMFhZPHyukibp3747ly5fj8uXLsLGxwZgxYzBo0CDs2LEDSmXl0+KJtB23OomqISoqCu+++y7mzZsHf39/SJ51KE9LKBQK7NixAzKZDDdv3sSsWbPwwQcfwMzMTOxoRDWGxUdUBYIg4IcffsDPP/+MLVu24NVXXxU7Uq1JSEiATCbDgQMH8N5772HWrFno0qWL2LGIXhi3OomeU0FBAcaMGYPdu3cjKSlJp0sPAJycnLB161acPHkShoaGsLe3x9ixY3HkyBE+Fo20GouP6Dmkp6fD0dERbdq0QWxsrF7dAdmpUycsWbIE2dnZcHV1hbe3NxwdHbFp0yaORyKtxK1OomcIDw+Hj48PFi1ahA8++EDsOKJTKpXYs2cPZDIZLly4gJkzZ2LatGlo3ry52NGInguLj+gJlEolvvzyS2zcuBHbt2+Hg4OD2JE0zsmTJxEYGIhdu3ZhwoQJmD17NiwtLcWORfRU3OokqsSdO3cwbNgwHD9+HMnJySy9J7C1tcX69etx7tw5tGjRAoMGDcKIESMQHR3N64CksVh8RP9x4sQJODg4wMbGBlFRUWjVqpXYkTRe27Zt8f333yM7OxseHh6YNWsWbGxssG7dOpSWloodj6gCbnUS/UtISAg++ugjrFixAuPGjRM7jtYSBAH79++HTCbDyZMn4evri+nTp6NNmzZiRyNi8REBD0cJffjhh9i3bx/Cw8PRu3dvsSPpjHPnziEoKAh//PEHRo0ahYCAAPTp00fsWKTHuNVJei83Nxdubm64evUqEhMTWXo1rFevXli1ahUuXLiAbt26YciQIZBKpdizZw9UKtWzP4CohnHFR3rt6NGjGD9+PHx8fDBv3jyNGyWki8rLy/HHH39AJpPhwYMH6vFIDRs2FDsa6QkWH+klQRCwYsUKfPvtt/j9998xfPhwsSPpHUEQcPjwYchkMhw5cgSTJ0/GzJkz0aFDB7GjkY7jX29J75SUlMDb2xurVq3CsWPHWHoikUgkePXVVxEeHo6EhASUlJSgb9++mDhxIpKSksSORzqMxUd6JSsrCwMGDEBZWRni4+PRvXt3sSMRgG7duiEoKAhXrlxRPxN04MCB2L59O8cjUY3jVifpjf3798PLywv/+9//MHv2bJ0ZJaSLFAoFwsPDIZPJkJubi1mzZmHy5Mkcj0Q1gsVHOk8QBPz4448ICgrC5s2b4eLiInYkqoLjx48jMDBQPQNx1qxZWjn0lzQHtzpJpxUWFmLcuHEIDw9HYmIiS08LvfLKK9i8eTNSU1NRv359ODo6YvTo0Th8+DAfi0bVwuIjnZWRkYFXXnkFLVq0QFxcHO8W1HIdO3bE4sWLkZWVBXd3d0yePBn9+vXDxo0bUV5eLnY80iLc6iSdFBERgWnTpmHhwoWYMmWK2HGoFqhUKvV4pPPnz2PGjBmYNm0aWrRoIXY00nAsPtIpSqUSX331FUJDQxEWFgZHR0exI1EdOHXqFIKCghAREYHx48djzpw5sLKyEjsWaShudZLOuHv3Lt544w0cO3YMycnJLD098mgSRHp6Otq0aQMXFxcMHz4c+/fv53VAegxXfKQTTp06hdGjR2P06NFYtGgRjIyMxI5EIiotLcXGjRshk8kgkUgwZ84cvPPOOzAxMRE7GmkAFh9pvQ0bNiAgIADLly+Hp6en2HFIgwiCgAMHDkAmkyElJQW+vr7w8/PjeCQ9x+IjrSWXy/Hxxx9jz549CA8P56gbeqr09HQsW7YMW7ZsgYeHB+bMmQNra2uxY5EIeI2PtNKNGzfg7u6OS5cuITk5maVHz9SzZ0+sXLkSFy9exEsvvYThw4fD3d0dkZGRHI+kZ7jiI60THx+Pt99+G5MnT8ZXX33FUUJULeXl5di2bRtkMhkKCgowe/ZsvP/++xyPpAdYfKQ1BEHAqlWr8NVXX2Ht2rUYMWKE2JFIBwiCgCNHjkAmk+HQoUPq8UgdO3YUOxrVEv5VmbRCSUkJJk+ejODgYBw7doylRzVGIpFg0KBB2LFjBxITE1FWVgZra2tMmDABiYmJYsejWsDiI42XnZ2NQYMGobi4mKOEqFZZWFggMDAQV65cgaOjI8aPH48BAwYgLCwMCoVC7HhUQ7jVSRrtwIEDmDRpEj799FMEBARwlBDVKYVCgZ07d0ImkyEnJwf+/v6YMmUKmjRpInY0egEsPtJIgiBgyZIlkMlk2LRpEwYPHix2JNJzSUlJkMlk2Lt3L7y8vDBr1ix069ZN7FhUDdzqJI1TWFiIt99+G2FhYUhMTGTpkUbo168fNm3ahLS0NJiamuKVV17BqFGjcOjQIT4WTcuw+EijnD9/Hk5OTmjSpAkOHTrEO+tI43To0AGLFi1CdnY2Xn/9dUydOhUODg7YsGEDxyNpCW51ksbYtWsXpkyZgvnz52PatGlixyF6LiqVCn/99RdkMhnS09Ph5+cHHx8ftGzZUuxo9AQsPhKdUqnEt99+i3Xr1mHbtm1wcnISOxJRtaSlpSEwMBDh4eF4++23MWfOHPTs2VPsWPQf3OokUd27dw8jR45EXFwckpOTWXqk1fr27Yu1a9ciIyMDbdu2xeDBgzFs2DDs27eP1wE1CFd8JJq0tDSMGjUKb775Jn788UcYGxuLHYmoRpWWlmLTpk0IDAyESqVSj0cyNTUVO5peY/GRKDZt2oTZs2cjKCgIEydOFDsOUa0SBAExMTGQyWRISkqCj48P/Pz8YG5uLnY0vcTiozoll8vx6aefYvfu3dixYwf69u0rdiSiOpWZmYmgoCBs3rwZb775JgICAmBjYyN2LL3Ca3xUZ27evAmpVIrMzEwkJSWx9EgvWVpaYsWKFbh06RJ69uyJESNGYPDgwdi1axfHI9URrvioTiQkJGDcuHH44IMP8PXXX3OUENE/5HK5ejxSfn6+ejxSo0aNxI6ms1h8VKsEQcDq1avx5ZdfYs2aNRg5cqTYkYg0kiAIOHbsGGQyGWJjY/HBBx/A39+fD3GoBfxrN9Wa0tJSTJ06FcuWLcORI0dYekRPIZFI1JMgkpKSoFAoYGNjA09PTyQkJIgdT6ew+KhWXL16FYMGDUJBQQGOHz+Ol156SexIRFqja9euWLp0Ka5cuQInJydMnDgRzs7O+OOPPzgeqQZwq5Nq3MGDBzFx4kR8+OGH+PjjjzlKiOgFKZVK9Xikq1evqscjNW3aVOxoWonFRzVGEAQsXboUS5YswcaNG+Hu7i52JCKdk5ycjMDAQPz555+YNGkSZs+ezfFIVcStTqoRRUVF8PT0xObNm3H8+HGWHlEteTQJ4vTp02jUqBGcnJzg4eGBuLg4PhbtObH46IVduHABzs7OaNiwIY4cOYLOnTuLHYlI57Vv3x4LFy5EdnY2hg4dCh8fH9jb2yMkJITjkZ6BW530QiIjI/HBBx/gu+++g4+PD6/nEYlEpVJh7969kMlkOHv2LPz8/ODr68vxSJXgio+qRaVS4ZtvvoGvry927twJX19flh6RiAwMDDB8+HDs378fUVFRyMrKQo8ePTBt2jScO3dO7HgahcVHVfZolFBMTAySk5Ph7OwsdiQi+pc+ffrgt99+Q2ZmJjp06AB3d3cMHToUUVFRvA4IbnVSFZ0+fRqjRo3CiBEjsGTJEo4SItICZWVl2Lx5M2QyGeRyOebMmQMvLy+9HY/E4qPntmXLFvj7+0Mmk2HSpElixyGiKhIEAQcPHoRMJsPx48cxbdo0zJgxA23btq3yZ90uKkNYSg4ybhSgoFQBMxMjWJmbYZx9B7RoVL8W0tccFh89k0KhwNy5cxEeHo4dO3ZwhAqRDjh//jyCgoKwadMmjBw5EgEBAbC1tX3mr0u9lo/g2IuIO58HAChT/N9ECRMjAwgAXC1bwc+lO6w7Nq2l9C+GxUdPdevWLYwfPx7169fHpk2b0Lx5c7EjEVENunv3Ln777TcsX74c3bp1Q0BAAEaMGAFDQ8PH3rshIQsL/sxAqUKJpzWHRAKYGBli3nArTHLqUnvhq4nFR0+UmJiIsWPH4t1338W3335b6Q8CEekGuVyO7du3QyaT4c6dO5g1axa8vb3RuHFjAI9KLx0l8uefGWhqbIB5w3tqXPmx+KhSv/32Gz7//HOsXr0aHh4eYschojoiCALi4+Mhk8kQExMDb29vSMdPRsDubJTIler33Y5citKsU1CWFMCgXgPUM++OZi7voZ55xcenmRobYus0J/Tt0LSOfydPxuKjCsrKyuDv748jR44gPDwclpaWYkciIpFkZWVh+fLl2HLdDMZd7ADJ/52Au7HxfzBs3AIG9RugNDsNirvXYWjWCh381lX4DIkEGNKrDX6Z5FDX8Z+IxUdqOTk5GDNmDDp27Ih169aptziISH/dLipD/0XRKFc+uSrKblzEjd/nABIDdPp4BySGRhVer29kgGNz3TTmbk8eYCcAQGxsLBwdHTF69Ghs27aNpUdEAICwlJwnPpWpIGU37kStwO1dSwAAZo4ej5UeAEgAhJ3Iqc2YVfJ4QtIrgiAgMDAQixcvRmhoKF577TWxIxGRBsm4UVDhyMK/FWccRdm1MwAAw8YtUb99r0rfV6pQISO3sNYyVhWLT489ePAAU6ZMQWZmJhISEtClSxexIxGRhikoffLEd/N3FkFQlKPk8gnkhS9EXsQPaO/zK4yatK7kc+S1GbNKuNWppy5evAgnJyfUr18fR48eZekRUaXMTB5fH6nkZRBUD+/wlBjVg6mFPST1TACVEor8G0/4HM15vCFXfHpoz5498Pb2xjfffIPp06dzqgIRPZGVuRnqG92osN1Z/ncmbu/+f6jfsTcMTBqh7NpZCGXFMGjQBPXaPD4N3sTIAFZtNee+ARafHlGpVJg/fz5Wr16NiIgI9O/fX+xIRKThxtp3wNL9mRW+Zti4BYyatUPplVNQlZfAsIEZGlgNRJMBnjAwafjYZwgAxtp1qKPEz8bi0xP5+fnw8vLCvXv3kJSUVK2H0hKR/ok/uA8ll0/BsJPtw0N5AIybt4f5O4ue69dLJMBgy1Yac5QB4DU+vXDmzBk4OjqiS5cuiImJYekR0TMVFhZi6tSpmD17NuZPGATTetVbJ5kYGcLPtXsNp3sxLD4d98cff2Dw4MH44osvsHz5ctSrV0/sSESk4Y4cOQIbGxsIgoDU1FS8N9IV84ZbwdS4apXx8FmdVhr1uDKAW506S6FQ4LPPPkNYWBj27dv3XONGiEi/lZeX4+uvv8bvv/+OX375BW+99Zb6tUcPmtaF6QwsPh2Ul5cHT09PGBkZITk5GS1atBA7EhFpuDNnzmDSpEno0qULUlNT0br142fxJjl1Qd8OTbEi9iIOZuZBgoeH0x95NI9vsGUr+Ll217iV3iN8VqeOSU5OxpgxY/DOO+/g+++/5yghInoqlUoFmUyGRYsWYfHixfD29n6uI053isoQdiIHGbmFKCiVw8zEGFZtG2OsHSewUx1au3Yt5s6di1WrVmH06NFixyEiDZednY333nsPKpUK69evR9euXcWOVCd4c4sOKCsrg6+vL3788UccOnSIpUdETyUIAtavXw8HBwcMHz4cBw8e1JvSA3iNT+vl5ORg7NixaNu2LRITE2FmZiZ2JCLSYHl5efDx8cHFixdx4MABWFtbix2pznHFp8Xi4uLg6OiIt956C9u3b2fpEdFTRUZGwtraGt27d0dSUpJelh7AFZ9WEgQBy5Ytw8KFCxEaGorXX39d7EhEpMGKiorw4YcfYv/+/diyZQteffVVsSOJisWnZYqLizF16lScO3cOCQkJerUvT0RVd/ToUbz77rtwcXFBamoqd4bArU6tcvnyZTg7O8PQ0BBHjx5l6RHRE5WXl+Pzzz/HmDFj8NNPP2Ht2rUsvX+w+LTEX3/9BWdnZ0ydOhXr169HgwYNxI5ERBrqzJkzeOWVV3DmzBmkpqbCw8ND7EgahcWn4R6NEpoyZQq2b9+OmTNncn4eEVVKpVJh6dKlGDx4MGbOnImdO3eiTZs2YsfSOLzGp8Hu37+P9957D3l5eUhKSkK7du3EjkREGio7Oxvvv/8+5HI5jh8/DgsLC7EjaSyu+DTUuXPn4OjoiPbt2+PgwYMsPSKqlCAICAkJgYODA4YOHYq4uDiW3jNwxaeBwsLCMH36dCxZsgTvv/++2HGISEPdvn0bPj4+OH/+PPbv3w8bGxuxI2kFrvg0iEKhwNy5c/Hxxx9j7969LD0ieqI9e/bA2toaFhYWSEpKYulVAVd8GuL27dvw9PQE8HDCQsuWLUVORESaqKioCB999BGioqKwadMmuLi4iB1J63DFpwFSUlLg4OAABwcH7N27l6VHRJWKj4+HjY0NysvLkZaWxtKrJq74RPb777/jk08+wcqVKzF27Fix4xCRBiovL8e3336LNWvWYOXKlRg1apTYkbQai08k5eXlmDNnDqKjoxEXF4devXqJHYmINNC5c+cwadIktG/fHqdOnYK5ubnYkbQei68G3C4qQ1hKDjJuFKCgVAEzEyNYmZthnH3lk4j//vtvjB07Fq1bt0ZiYiKaNGkiQmoi0mQqlQrLli3DggUL8MMPP2Dy5Ml8eEUN4QT2F5B6LR/BsRcRdz4PAFCmUKlfMzEygADA1bIV/Fy6w7pjUwDA4cOH4enpCT8/P3z22WcwMOBlViKq6OrVq/D29kZpaSlCQkLQrVs3sSPpFBZfNW1IyMKCPzNQqlDiaX+CEglgYmSIz4dZIT95N+bPn4/169dj6NChdReWiLSCIAjYuHEjPvzwQ3z44Yf45JNPYGhoKHYsncPiq4aHpZeOErnq2W/+h4FKgfrn9mBP0P/4VAUiesydO3fg6+uL9PR0bNiwgefyahH32aoo9Vo+FvyZ8VjpCYpy3N33C64tewdX/99o3Aj9BGV/Z6pfVxkYQbAdhaJ6zes6MhFpuL/++gt9+/ZFp06dkJyczNKrZSy+KgqOvYhShfKxr989sBqFJyJh2LApTHs4oex6Bm5u+QLK4vvq95QpVFgRe7Eu4xKRBnvw4AGmT5+O6dOnY+PGjfjpp59gYmIidiydx+KrgttFZYg7n/fYNT3lg3wUpR0AJAZo47kArd76FA17u0IoL0FhSqT6fYIAHMzMw52isjpOTkSaJiEhATY2NigpKUFqaipcXV3FjqQ3WHxVEJaSU+nX5bevAioFDM1awbBhUwBAPfPuAIDyW1cqvFcCIOxE5Z9DRLpPLpfjyy+/hIeHBxYvXozff/+dR5rqGM/xVUHGjYIKRxYeUT64BwAwqPd/WxSSf/750WuPlCpUyMgtrMWURKSpzp07By8vL5ibm/Mwuoi44quCglJFpV83bNgMAKAqL1V/Tfjnnx+9VvFz5LWQjog0lUqlQlBQEFxcXODj44PIyEiWnoi44qsCM5PK/7iMW3YEDIygLMiD8sE9GDZshrLc8wCAeq27VvI5xrWak4g0x7Vr1+Dt7Y3i4mLEx8eje/fuYkfSe1zxVYGVuRnqGz3+R2bYsBka9XEHBBVubp6HvJ2LUXzuECT1TNHYfkSF95oYGcCqbeO6ikxEIhEEARs2bIC9vT3c3Nxw6NAhlp6G4IqvCsbad4DswPlKX2smnQYYGqE4/TDk93JRv70lmrlNhmGDihetS8vKYHwtBQpFZxgZ8Y+fSBfduXMH06dPx9mzZ7F3717Y2dmJHYn+hU9uqaJpocnYn37zqY8pexKJBHi5qRL5u5cgOzsb/v7+mDp1Kpo2bVrjOYlIHHv37sWUKVPw9ttvY+HChTyXp4G41VlFM1y7w8Soes/OMzEyxIKJr+Lw4cPYsWMHTp06BQsLC/j7++PiRR5sJ9JmDx48gJ+fH3x8fBASEoKlS5ey9DQUi6+KrDs2xbzhVjA1rtofnamxAeYNt0LfDk0BAA4ODti4cSNOnz6NRo0awdnZGW+99RZiY2PBRTiRdjl+/DhsbW1RVFSE1NRUuLm5iR2JnoJbndVU1ekM84ZbYZJTlye+78GDBwgJCUFgYCAaNGiAgIAAeHp6ol69ejUfnohqhFwux/fff49Vq1YhODgYY8eOFTsSPQcW3wtIy8nHT3vPIDYzD6YmJiitZB7fYMtW8HPtrl7pPYtKpcLevXshk8lw9uxZ+Pn5wdfXFy1btqyd3wQRVUt6ejq8vLzQunVrrFmzBm3bthU7Ej0nFt8LWrlyJWLjk+E25XNk5BaioFQOMxNjWLVtjLF2lU9gf16nT59GYGAgduzYgXHjxmHOnDno1atXDaYnoqpSqVT4+eef8f3332P+/PmYNm0aJ6NrGRbfC3r99dfh4+ODMWPG1Nr3uHXrFlauXImVK1fCxsYGAQEBeP311/nDRlTHcnJy4O3tjaKiIoSEhKBHjx5iR6JqYPG9gHv37qFz587Izc1Fw4YNa/37lZaWYvPmzZDJZFAoFJgzZw68vLxgampa69+bSJ8JgoDNmzdjzpw5mD17NubOnctzuFqMxfcCNmzYgG3btmHnzp11+n0FQUBMTAxkMhkSExMxbdo0zJgxg9cYiGrB3bt3MX36dJw+fRqhoaGwt7cXOxK9IB5neAHh4eEYNWpUnX9fiUQCd3d3REZG4vDhw7h79y569eqFd999FydPnqzzPES6KioqCn379kW7du2QkpLC0tMRXPFVU0lJCczNzXHp0iWNuOPy7t27+PXXX/Hzzz+jW7duCAgIwIgRI2BoWL3D9kT6rLi4GJ9++il27dqFdevWwd3dXexIVIO44qumffv2wc7OTiNKDwCaN2+OuXPn4vLly/Dx8cGCBQtgaWmJ5cuXo6ioSOx4RFojMTERtra2uH//PtLS0lh6OojFV00RERGibHM+i7GxMSZMmIDjx49j/fr1iIuLQ+fOnfHJJ5/g6tWrYscj0lhyuRzffPMNRo4cifnz5yM0NJTP0dVRLL5qUCgU2L17Nzw8PMSO8kQSiQQDBgxAWFgYkpOToVQqYWtri/HjxyMhIUHseEQaJSMjA/3798fx48dx8uRJjBs3TuxIVItYfNVw+PBhdOnSBZ06dRI7ynPp2rUrli5diitXrsDZ2RkTJ06Ek5MTtm7dCoWi8qnyRPrg0WH0gQMHYvLkyfjzzz/Rrl07sWNRLePNLdUwa9YstGnTBvPmzRM7SrUolUrs3LkTMpmM45FIb12/fh3e3t4oKChAaGgoD6PrEa74qkgQBI29vve8DA0NMXr0aPV4pNTUVI5HIr2yefNm2NraYtCgQThy5AhLT8+w+KooJSUFpqam6Nmzp9hRaoSDgwM2bNiA06dPo3HjxhyPRDrt7t27mDBhAr777jv8+eef+PLLL/kEFj3E4qui8PBweHh46NxzMtu3b4+FCxciOzsbw4YNg6+vL+zs7BASEoLy8nKx4xG9sH379sHa2hqtW7fGiRMn4ODgIHYkEgmv8VVRr169sHbtWjg5OYkdpVZxPBLpiuLiYsydOxc7d+7E2rVrIZVKxY5EIuOKrwoyMzORn58PR0dHsaPUOgMDAwwfPhz79+9HVFQUrly5gh49emDq1Kk4e/as2PGInktSUhLs7Oxw9+5dpKamsvQIAIuvSiIiIuDh4QEDA/36Y+vTpw/WrFmDzMxMdOjQAe7u7hgyZAj27t3L64CkkeRyOb799luMGDEC3333HTZu3IhmzZqJHYs0BLc6q8DJyQnff/89XnvtNbGjiKq0tBRbtmyBTCaDXC7neCTSKJmZmfDy8kLz5s2xZs0atG/fXuxIpGH0a+nyAq5fv47z58/D1dVV7CiiMzExwfvvv49Tp07h559/xu7du9G5c2d88cUXyM3NFTse6SlBEBAcHIwBAwbg/fffx19//cXSo0qx+J7Tzp078cYbb8DY2FjsKBpDIpHAzc0Nu3fvxpEjR3Dv3j2ORyJRXL9+HUOHDkVISAiOHj0KPz8/nbvzmmoOi+85iTV7T1u89NJLCA4OxqVLl9C7d2+8+eabcHV1xc6dO6FUKsWORzps69atsLOzw4ABA3D06FFYWlqKHYk0HK/xPYd79+6hc+fOyM3NRcOGDcWOoxXkcjnCwsIgk8lw9+5dzJ49G97e3mjUqJHY0UhH3Lt3DzNmzMCJEycQGhqKfv36iR2JtARXfM8hMjISgwcPZulVwZPGI3388cfIzs4WOx5puQMHDsDa2hotW7bEiRMnWHpUJSy+56Dtz+YU03/HIwmCADs7O7z99tuIj48XOx5pmeLiYsyaNQve3t5Ys2YNli1bhgYNGogdi7QMtzqfoaSkBObm5rh8+TJatGghdhydUFBQgHXr1iEoKAitW7dGQEAAxowZw2cm0lMlJyfDy8sLtra2CA4O5rk8qjau+J5h3759sLe3Z+nVIDMzM8yePRsXLlzA3LlzERwcDAsLCyxZsgT5+flixyMNo1Ao8N1332H48OH4+uuvsWnTJpYevRAW3zPwbs7aY2hoiFGjRuHQoUMIDw/neCR6zPnz5zFw4EAcPXoUJ0+ehKenp9iRSAew+J5CoVAgMjISHh4eYkfRefb29hyPRGqCIGDFihXo378/vLy8sHfvXh5GpxrDa3xPERMTg7lz5yIpKUnsKHqnuLgYISEhCAwMhKmpKQICAjB+/HjUr19f7GhUy/7++2988MEHuHv3LkJDQ3kuj2ocV3xPwW1O8TRo0AC+vr44d+4cFixYgNDQUHTp0gXff/898vLyxI5HteSPP/6Ara0tnJ2deRidag1XfE8gCAI6deqEqKgo9OrVS+w4BOD06dMICgrC9u3bMXbsWMyZMwe9e/cWOxbVgPz8fMycORNJSUnYsGEDz+VRreKK7wlSUlLQoEED9OzZU+wo9I8+ffrgt99+Q2ZmJjp27AipVMrxSDogOjoaffv2RbNmzXDy5EmWHtU6rvieYN68eVAqlVi0aJHYUegJysrKsHnzZo5H0lIlJSX47LPPEBYWhrVr1+L1118XOxLpCa74noDX9zRf/fr1OR5JS6WkpMDe3h43b95EWloaS4/qFIuvEpmZmbh//z63XLQExyNpD4VCgfnz52PYsGH48ssvsXnzZjRv3lzsWKRnWHyVCA8Ph4eHBwwM+MejbTgeSXNduHABgwYNwqFDh3DixAlMmDBB7Eikp/hf9kpwm1P7NW/eHHPnzsXly5fh6+uLhQsXwtLSEsuWLUNhYaHY8fSKIAhYuXIl+vfvj4kTJ2Lv3r3o0KGD2LFIj/Hmlv+4fv06+vTpg5s3b3Laug4RBAHx8fGQyWSIiYmBt7c3/P390blzZ7Gj6bTc3FxMnjwZt27dwoYNG2BlZSV2JCKu+P4rIiICb7zxBktPx0gkEvTv3x/btm1DSkoKxyPVgW3btsHGxgb9+vVDfHw8S480Bld8/yGVSuHn54fRo0eLHYVqGccj1Y78/Hz4+/sjMTERoaGhcHR0FDsSUQUsvn+5d+8eOnfujNzcXE5b1yNKpRK7du2CTCZDVlYW/P39MXXqVDRt2lTsaFrn0TbyiBEj8OOPP/LniDQStzr/JTIyEm5ubvxh1TMcj/TiSkpKEBAQgHfffRerV69GcHAwf45IY7H4/oV3c9K/xyOZmZmhf//+HI/0DCdOnICDgwP+/vtvpKamYsiQIWJHInoqbnX+o7i4GG3btsWVK1d4oJbUiouLERoaisDAQJiYmGDOnDnw9PTkeCQ8PIy+ePFiBAUFITAwEBMmTIBEIhE7FtEzsfj+ERERgeXLlyM6OlrsKKSBVCoVoqKiIJPJcObMGUyfPh2+vr5o1aqV2NFEcfHiRXh5eaFhw4ZYt24dOnbsKHYkoufGrc5/cJuTnsbAwADDhg3Dvn37sG/fPmRnZ+Oll17C1KlTcfbsWbHj1RlBELBq1So4OztjwoQJ2LdvH0uPtA5XfADkcjnMzc1x6tQp/hDTc7t16xZ++eUXrFy5En379kVAQACGDBmis9t9ubm5mDJlCm7evInQ0FCO7CKtxRUfgEOHDsHCwoKlR1XSunVrfPXVV8jKysKECRMwd+5c9O7dG6tXr0ZJSYnY8WrU9u3bYWtrC3t7e8THx7P0SKtxxQfA398fbdu2xeeffy52FNJigiDg4MGDCAwMREJCAqZNm4YZM2agbdu2Ykertvv378Pf3x/x8fEIDQ2Fk5OT2JGIXpjer/gEQUBERASv79ELezQeadeuXTh69Cjy8/PRq1cveHl54cSJE2LHq7KDBw/C2toajRo1wqlTp1h6pDP0vviSk5PRsGFDbt1QjerRowd+/vlnXL58GX369MFbb70FFxcXREREaPx4pNLSUnz44YeYNGkSVq5ciRUrVvAwOukUvS8+3s1JtalZs2b49NNPcfnyZUyfPh0//PCDRo9HOnnyJBwcHJCTk4O0tDQMGzZM7EhENY7Fx+KjOmBsbAxPT08kJCQgJCQEhw8fRpcuXfDxxx8jOztb7HhQKBRYuHAhhgwZgs8++wxbt25FixYtxI5FVCv0+jH0GRkZKCwshIODg9hRSE88Go/Uv39/ZGVlYfny5bCzs4O7uzsCAgLg7Oxc7c++XVSGsJQcZNwoQEGpAmYmRrAyN8M4+w5o0ejJT5q5dOkSvLy8YGpqipSUFN7dTDpPr+/q/OGHH5CTk4Pg4GCxo5AeKywsVI9HatWqVZXHI6Vey0dw7EXEnc8DAJQpVOrXTIwMIABwtWwFP5fusO7YVP2aIAj49ddfMW/ePHzxxRfw9/eHgYHebwKRHtDr4nN0dMTChQshlUrFjkIEpVKJ3bt3QyaT4cqVK881HmlDQhYW/JmBUoUST/tJlkgAEyNDzBtuhUlOXXDjxg1MmTIFubm5CA0NRa9evWr+N0SkofT2r3c5OTm4dOkSXFxcxI5CBODheCQPDw/ExcUhPDwcaWlpsLCwwMyZM3HhwoXH3v+w9NJRIn966QGAIAAlciUW/JmOj36JgI2NDWxtbREfH8/SI72jtyu+4OBgHD9+HCEhIWJHIXqiv//+G8HBwVi9ejWcnZ0REBAAV1dXpOXch+evCSiR/9/RiDt/LkPp9XNQFtyGxNAY9dq9hGaDvVGvVZeKH6oox3y3lpg0bFDd/maINITervh4Nydpg3bt2mHBggXIzs7GG2+8AT8/P9jZ2WFuSAxK5RXPAxal7YNB/YZo2OtVSOo3QOnlFNz642sIivIK75MY1cORO6Z1+dsg0ih6ueK7e/cuunbtitzcXDRo0EDsOETPTaVSYdvuvfjfMTkEg4o3v5TduIj65t0BAIr8m7j+y2QAgPn7geqvP1LfyADH5ro99W5PIl2llyu+yMhIuLm5sfRI6xgYGOBeU0vUq1fvsdf+XW6CSvHwHyQGMGz0+GBlCYCwEzm1FZNIo+ll8XGbk7RZxo2CCkcW/ktVXoI7ewIBAGaOHjCqpPhKFSpk5Grek2OI6oLeFV9xcTGio6MxYsQIsaMQVUtBqeKJrymL7+Pmps9Rdj0djayHoKmr91M+R14b8Yg0nt49uSUqKgr9+vVD8+aP/y2YSBuYmVT+Y6u4fws3t34Jxd3rMHMeh2Yu7z3jc4xrIx6RxtO74uMIItJGZWVliI+Px4EDB3Ag8wGEzoMgMa54Y8qN0I+hLLoLQ7NWEORluHtgNQCgYS8X1G9nWeG9JkYGsGrbuM7yE2kSvbqrUy6Xw9zcHKmpqejQoYPYcYieSKVSITU19WHRHTiAY8eOoXfv3pBKpeg30A2fHC1D+X+u82Uvqnz7vsXwOWjUt+LTiXhXJ+kzvVrxHTp0CN26dWPpkUa6fPmyuugOHjyIli1bwt3dHdOnT8fWrVsrPLpsT14y9qffrPDEls7/i3yu7yORAIMtW7H0SG/pVfHxbk7SJHl5eYiJiUF0dDQOHDiAkpISSKVSvPHGG1i6dOlT/4I2w7U7Dl+4XeHJLc/LxMgQfq7dn/1GIh2lN1udKpUKnTp1woEDB2BlZSV2HNJDDx48wJEjR9SrusuXL8PFxQVSqRTu7u7o1asXJBLJc3/e/z2r88lHG/7L1NgA84b3xCSnLtX4HRDpBr1Z8SUnJ6Nx48YsPaozCoUCycnJ6qJLTk6Gvb093N3dERwcjH79+sHYuPp3Vj4qr+pMZyDSZ3qz4vvss88gkUiwcOFCsaOQjhIEARkZGeqii4uLQ+fOnSGVSiGVSjFo0CA0atSoxr9vWk4+VsRexMHMPEjw8HD6I4/m8Q22bAU/1+7o26FpjX9/Im2jN8VnZWWFkJAQODo6ih2FdMj169cRHR2tvk5nZGSE1157DVKpFG5ubmjdunWdZblTVIawEznIyC1EQakcZibGsGrbGGPtnj6BnUjf6EXxpaen47XXXsPVq1c5YZpeyP379xEXF6de1d28eRNubm7q63TdunWr0nU6Iqp7enGNLyIiAh4eHiw9qrKysjIkJCSoi+7MmTNwcnKCVCpFaGgobGxsYGhoKHZMIqoCvVjxOTo64ocffoC7u7vYUUjDqVQqpKWlVTg4bmVlpb5O179/f5iYmIgdk4hegM4XX05ODqytrXHjxo0XuoOOdNeVK1fU1+iio6PRvHlzddG5urqiWbNmYkckohqk81udERERGDFiBEuP1G7fvo2DBw+qV3UPHjyAVCrFkCFD8OOPP6JTp05iRySiWqTzxRceHg5/f3+xY5CIiouLKxwcv3TpEgYNGgSpVAp/f3/07t2bN6QQ6RGd3uq8c+cOLCwskJuby2nrekShUCAlJUW9dZmYmAhbW1v19qWjoyN3AIj0mE6v+CIjI+Hm5sbS03GCICAzM1N9nS42NhYdO3aEVCrFRx99hFdffRWNG3MEDxE9pNPFFx4ejtGjR4sdg2pBbm6uuugOHDgAAwMDSKVSjBs3DitXroS5ubnYEYlIQ+nsVmdxcTHMzc2RlZXFaes6oKCgoMLB8dzcXAwePFi9fdm9e3depyOi56KzK76oqCg4Ojqy9LRUeXm5+uB4dHQ00tLS8Morr0AqlWL9+vWwtbXlwXEiqhadLT7O3tMuKpUKp0+fVm9fHjlyBJaWlnB3d8e3336LAQMGwNTUVOyYRKQDdHKrUy6Xw9zcHGlpaWjfvr3YcegJsrOz1VuX0dHRaNKkiXrrcvDgwVytE1Gt0MkVX1xcHLp3787S0zB37typcHC8sLAQ7u7ueO2117Bo0SJ07txZ7IhEpAd0svi4zakZSkpK1AfHo6Ojcf78efXBcT8/P7z88st8cDgR1Tmd2+pUqVTo2LEjoqOjOW29jimVSqSkpKiv0yUmJsLa2hru7u6QSqV45ZVXUK9ePbFjEpGe07kVX1JSEszMzFh6dUAQBFy4cEG9dRkbG4t27dpBKpUiICAAr776KszMzMSOSURUgc4VX0REBLc5a9GNGzcqTDIQBAFSqRRjxoxBcHAw2rZtK3ZEIqKn0rmtTisrK4SGhqJfv35iR9EJhYWFiIuLU5ddTk4OBg8erN6+fOmll3hwnIi0ik6t+NLT0/HgwQM4ODiIHUVryeVyHD9+XL19eerUKTg6OkIqlWLNmjWws7ODkZFO/d+GiPSMTv0XLDw8HB4eHlyBVIEgCDhz5oy66A4fPowePXpAKpXi66+/xoABA/iQbyLSKTq11dmvXz8sXrwYbm5uYkfRaFevXlUXXUxMDBo1alTh4HiLFi3EjkhEVGt0pviuXbsGW1tb3Lhxg1tx/3Hv3r0KB8fz8/Ph7u6u/l/Xrl3FjkhEVGd0piEiIiIwYsQIlh6A0tJSHD16VF10GRkZGDhwIKRSKXx8fNCnTx8eHCcivaUzLREeHo5Zs2aJHUMUSqUSJ0+eVBddQkIC+vbtC6lUip9++glOTk48OE5E9A+d2Oq8c+cOLCwskJubqxc3YgiCgIsXL6rP0h08eBDm5ubq63QuLi48OE5E9AQ6seKLjIyEu7u7TpfezZs3ER0drT5Pp1AoIJVK8dZbb2HZsmVo166d2BGJiLSCThRfeHg4xowZI3aMGlVUVIRDhw6pty+vXr0KV1dXSKVSfPLJJ7C0tOSxDSKiatD6rc4HDx6gXbt2yMrKQrNmzcSOU21yuRyJiYnqojt58iT69eun3r60t7fnjTtERDVA6/9LGhUVBUdHR60rPUEQcPbsWfV1ukOHDqFbt25wd3fHF198gYEDB6Jhw4ZixyQi0jlaX3zaNHvv2rVrFR7wbGpqCqlUCi8vL6xduxatWrUSOyIRkc7T6q1OuVyONm3a4PTp0xo5bf3evXuIjY1Vb1/euXNH/XBnd3d3WFhYiB2RiEjvaPWKLzY2Fj169NCY0istLcWxY8fURZeeno4BAwZAKpViy5YtsLa25sFxIiKRaXXxib3NqVQqcerUKfXWZXx8PF5++WW4u7vjxx9/hLOzM+rXry9aPiIiepzWbnWqVCp07NgRMTExsLS0rJPvKQgCLl26pL5OFxMTg9atW1c4ON60adM6yUJERNWjNSu+20VlCEvJQcaNAhSUKlBedB+mdm+iZfsutfp9b926hZiYGPX2ZXl5OaRSKUaOHInAwECN2WYlIqLno/ErvtRr+QiOvYi483kAgDKFSv2aIZQwMjKGq2Ur+Ll0h3XHpi/8/YqKinD48GH19mVWVhZcXFzUN6X07NmTB8eJiLSYRhffhoQsLPgzA6UKJZ6WUiIBTIwMMW+4FSY5danS95DL5UhKSlJvX6akpMDe3l69fdmvXz8eHCci0iEaW3wPSy8dJXLVs9/8D1NjA8wb3vOp5ScIAtLT09Vbl3Fxcejatau66AYNGsSD40REOkwjiy/1Wj48f01AiVyp/lpB0k4Upe2H/PZVQFChyYAJaDroncd+ramxIbZOc0LfDk3VX8vJyalwcLxevXp47bXX4O7uDjc3N7Ru3boufltERKQBNHIPLzj2IkoVygpfK79xEQYmjWDYuCWUBbee+GtLFUoE7U/HyGY31au6vLw8uLm5QSqV4ptvvoGFhQWv0xER6SmNK77bRWWIO5/32DW9liM/AgDc2j4fJU8pPkEADpy7gStnf8dQ1wHYtGkTbGxseHCciIgAaGDxhaXkvPBnmJqYYPz/lsLn1W41kIiIiHSJxi2DMm4UVDiyUB2lChUycgtrKBEREekSjSu+glJFDX2OvEY+h4iIdIvGFZ+ZSc3svpqZGNfI5xARkW7RuGt8VuZmqG9047HtzsLUKJRdO4fym5cAAMUXEqC4fwsNXnJCg5ecK7zXxMgAVm0b11lmIiLSHhq34htr36HSr5ddO4cHZ6KhLHj46DL5rSt4cCYa5TcvP/ZeAcBYu8o/h4iI9JtGHmCfFpqM/ek3n/qYsieRSIAhvdrgl0kONR+MiIi0nsat+ABghmt3mBgZVuvXmhgZws+1ew0nIiIiXaGRxWfdsSnmDbeCqXHV4j18VqdVhceVERER/ZvG3dzyyKMHTdf2dAYiItIvGnmN79/ScvKxIvYiDmbmQYKHh9MfMTEygABgsGUr+Ll250qPiIieSeOL75E7RWUIO5GDjNxCFJTKYWZiDKu2jTHWrgNaNKovdjwiItISWlN8RERENUEjb24hIiKqLSw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSKyw+IiLSK/8fD0mjO05Zdr8AAAAASUVORK5CYII=\n"
     },
     "metadata": {}
    }
   ],
   "source": [
    "g = nx.Graph()\n",
    "nx.add_path(g, [0, 1])\n",
    "nx.add_path(g, [1, 2])\n",
    "nx.add_path(g, [2, 3])\n",
    "nx.add_path(g, [3, 4])\n",
    "nx.add_path(g, [0, 4])\n",
    "nx.add_path(g, [0, 2])\n",
    "nx.draw(g, with_labels=True, font_weight='bold')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如上图，我们得到一个由5个节点和6条边构成的图结构。\n",
    "\n",
    "接下来我们用穷举法来看看所有情况的切割边数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "one size: [0] cut= 3\none size: [1] cut= 2\none size: [1, 0] cut= 3\none size: [2] cut= 3\none size: [2, 0] cut= 4\none size: [2, 1] cut= 3\none size: [3] cut= 2\none size: [3, 0] cut= 5\none size: [3, 1] cut= 4\none size: [3, 2] cut= 3\none size: [4] cut= 2\none size: [4, 0] cut= 3\none size: [4, 1] cut= 4\none size: [4, 2] cut= 5\none size: [4, 3] cut= 2\n"
    }
   ],
   "source": [
    "for i in g.nodes:\n",
    "    print('one size:', [i], 'cut=', nx.cut_size(g, [i]))            # 一组1个节点、另一组4个节点的所有情况\n",
    "    for j in range(i):\n",
    "        print('one size:', [i, j], 'cut=', nx.cut_size(g, [i, j]))  # 一组2个节点、另一组3个节点的所有情况"
   ]
  },
  {
   "source": [
    "从以上结果可以看出，穷举法得到的最大切割边数为5，如果对节点分组的左右进行区分，则一共有4种分组方法可以使切割边数最大，即该问题有4个简并解。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## QAOA算法整体流程\n",
    "\n",
    "1. 搭建QAOA量子线路，其中ansatz线路包含可以训练的参数\n",
    "2. 初始化线路中的参数\n",
    "3. 运行该量子线路，得到量子态$|\\psi\\rangle$\n",
    "4. 计算目标哈密顿量$H_C$的期望值$\\langle\\psi|H_C|\\psi\\rangle$\n",
    "5. 根据第4步的结果，使用Adam优化器优化线路中参数\n",
    "6. 重复3-5步，直到第4步结果基本不再变化\n",
    "7. 根据第4步的结果，算出目标问题的近似解\n",
    "\n",
    "在该流程中，第2-6步都可以由MindSpore和MindQuantum中现成的包和函数来实现，因此我们将重点关注第1步——量子线路的搭建。\n",
    "\n",
    "![Flowchart](https://gitee.com/mindspore/docs/raw/master/docs/mindquantum/docs/source_zh_cn/images/QAOA_Flowchart.png)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 搭建QAOA量子线路\n",
    "\n",
    "先前提到，我们需要将问题对应的哈密顿量\n",
    "\n",
    "$$\n",
    "H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2\n",
    "$$\n",
    "\n",
    "最小化来找到问题的解，也就是说我们要找到该哈密顿量的基态。对此我们可以采用量子绝热演化的方法，使系统先处于某一简单哈密顿量$H_B$的基态上，然后使简单的哈密顿量$H_B$绝热地、缓慢地演化至某一复杂的哈密顿量$H_C$，根据绝热定理，系统将始终保持在哈密顿量的基态上，最终达到复杂哈密顿量$H_C$的基态。\n",
    "\n",
    "我们将要搭建的量子线路就是采用以上思路，选取初始简单哈密顿量为\n",
    "\n",
    "$$\n",
    "H_B=\\sum_i X_i\n",
    "$$\n",
    "\n",
    "并将量子线路制备到$H_B$的基态$|s\\rangle=|+\\rangle^{\\otimes n}$，这里通过对所有量子比特作用`Hadamard`门即可实现。然后连接ansatz含参线路，通过不断地优化其中参数可以使得ansatz线路越来越接近真实绝热演化的效果，最终得到的量子线路可以视为模拟近似了一个真实的绝热演化过程。\n",
    "\n",
    "### ansatz线路\n",
    "\n",
    "在量子绝热演化中，首先选取初始哈密顿量\n",
    "\n",
    "$$\n",
    "H_B=\\sum_i X_i\n",
    "$$\n",
    "\n",
    "并使系统处于$H_B$的基态$|s\\rangle=|+\\rangle^{\\otimes n}$。然后缓慢地作用如下含时哈密顿量\n",
    "\n",
    "$$\n",
    "H(t)=(1-\\frac{t}{T})H_B+(\\frac{t}{T})H_C\n",
    "$$\n",
    "\n",
    "注意到当$t=T$时，$H(T)=H_C$。当选取的$T$足够大时（满足绝热条件），系统将始终处于$H(t)$的瞬时基态上，此时系统的量子态将从初始哈密顿量$H_B$的基态$|\\psi (0)\\rangle$绝热地演化到目标哈密顿量$H_C$的基态$|\\psi (T)\\rangle$上，即\n",
    "\n",
    "$$\n",
    "|\\psi (T)\\rangle=\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}|\\psi(0)\\rangle\n",
    "$$\n",
    "\n",
    "也就是说，ansatz线路需要模拟的就是$\\mathcal{T}e^{-i\\int^{T}_{0} H(t)dt}$这一演化过程。接下来我们将对这个式子进行一些近似和化简，使其变为可以在量子线路中实现的形式。\n",
    "\n",
    "考虑如下trotter公式\n",
    "\n",
    "$$\n",
    "\\mathcal{T}e^{-i\\int^T_0 H(t)dt}=\\lim_{N\\rightarrow \\infty}\\prod^N_{l=1}e^{-iH(t_l)\\Delta t},\\quad \\Delta t=\\frac{T}{N},\\quad t_l=l\\Delta t\n",
    "$$\n",
    "\n",
    "略去$O(\\Delta t^2)$项，得到\n",
    "\n",
    "$$\n",
    "\\mathcal{T}e^{-i\\int^T_0 H(t)dt}\\approx \\lim_{N\\rightarrow \\infty}\\prod^N_{l=1}e^{-iH_B(1-t_l/T)\\Delta t}e^{-iH_C t_l\\Delta t/T}\n",
    "$$\n",
    "\n",
    "令$\\beta_l=(1-t_l/T)\\Delta t$，$\\gamma_l=t_l\\Delta t/T$，并取$N$为一个有限大的整数，即得到QAOA的ansatz\n",
    "\n",
    "$$\n",
    "|\\psi(\\gamma,\\beta)\\rangle=\\prod^p_{l=1}e^{-i\\beta_l H_B}e^{-i\\gamma_l H_C}|\\psi_{in}\\rangle\n",
    "$$\n",
    "\n",
    "因此我们需要搭建的ansatz线路由$U_C(\\gamma)$和$U_B(\\beta)$这两个酉变换交替构成，其中$U_C(\\gamma)=e^{-i\\gamma \\sum_{\\langle i,j\\rangle}Z_i Z_j}$可以由`ZZ`门实现，$U_B(\\beta)=e^{-i\\beta \\sum_i X_i}$则相当于在每个量子比特上作用一个`RX`旋转门，$\\gamma$和$\\beta$是可训练的参数。"
   ]
  },
  {
   "source": [
    "搭建$U_C(\\gamma)$对应的量子线路："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hc(g, para):\n",
    "    hc = Circuit()                  # 创建量子线路\n",
    "    for i in g.edges:\n",
    "        hc += ZZ(para).on(i)        # 对图中的每条边作用ZZ门\n",
    "    hc.barrier()                    # 添加Barrier以方便展示线路\n",
    "    return hc"
   ]
  },
  {
   "source": [
    "线路展示："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖\n          │            │            │                                             ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖\n                       │            │            │                                ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖\n                       │                                      │                   ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖\n                       │                                                   │      ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖",
      "text/html": "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)─────────────────────────────────────────‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">          │            │            │                                             ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────────┼────────────┼────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────────────────────────────‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │            │            │                                ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ───────────────────┼────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)───────────────‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                                      │                   ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ───────────────────┼──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                                                   │      ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q4: ───────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)───────────────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)──‖</span>\n</pre>\n"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hc(g, 'gamma')\n",
    "circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建$U_B(\\beta)$对应的量子线路："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hb(g, para):\n",
    "    hb = Circuit()                  # 创建量子线路\n",
    "    for i in g.nodes:\n",
    "        hb += RX(para).on(i)        # 对每个节点作用RX门\n",
    "    hb.barrier()                    # 添加Barrier以方便展示线路\n",
    "    return hb"
   ]
  },
  {
   "source": [
    "线路展示："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──RX(beta)──‖\n                ‖\nq1: ──RX(beta)──‖\n                ‖\nq2: ──RX(beta)──‖\n                ‖\nq3: ──RX(beta)──‖\n                ‖\nq4: ──RX(beta)──‖",
      "text/html": "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q4: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n</pre>\n"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hb(g, 'beta')\n",
    "circuit"
   ]
  },
  {
   "source": [
    "实现了一层酉变换$U_B(\\beta) U_C(\\gamma)$的ansatz线路如下所示："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──ZZ(gamma)────ZZ(gamma)────ZZ(gamma)─────────────────────────────────────────‖──RX(beta)──‖\n          │            │            │                                             ‖            ‖\nq1: ──ZZ(gamma)────────┼────────────┼────────ZZ(gamma)────────────────────────────‖──RX(beta)──‖\n                       │            │            │                                ‖            ‖\nq2: ───────────────────┼────────ZZ(gamma)────ZZ(gamma)────ZZ(gamma)───────────────‖──RX(beta)──‖\n                       │                                      │                   ‖            ‖\nq3: ───────────────────┼──────────────────────────────────ZZ(gamma)────ZZ(gamma)──‖──RX(beta)──‖\n                       │                                                   │      ‖            ‖\nq4: ───────────────ZZ(gamma)───────────────────────────────────────────ZZ(gamma)──‖──RX(beta)──‖",
      "text/html": "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)─────────────────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">          │            │            │                                             ‖            ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────────┼────────────┼────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │            │            │                                ‖            ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ───────────────────┼────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)───────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                                      │                   ‖            ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ───────────────────┼──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                                                   │      ‖            ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q4: ───────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)───────────────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(gamma)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(beta)──‖</span>\n</pre>\n"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circuit = build_hc(g, 'gamma') + build_hb(g, 'beta')\n",
    "circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了使得最后优化的结果足够准确，我们需要将量子线路重复多次，因此我们通过如下函数搭建多层的训练网络："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ansatz(g, p):                    # g是max-cut问题的图，p是ansatz线路的层数\n",
    "    circ = Circuit()                       # 创建量子线路\n",
    "    for i in range(p):\n",
    "        circ += build_hc(g, f'g{i}')       # 添加Uc对应的线路，参数记为g0、g1、g2...\n",
    "        circ += build_hb(g, f'b{i}')       # 添加Ub对应的线路，参数记为b0、b1、b2...\n",
    "    return circ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建图对应的哈密顿量$H_C=\\sum_{(i,j)\\in C}(Z_iZ_j-1)/2$（忽略常数项和系数）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_ham(g):\n",
    "    ham = QubitOperator()\n",
    "    for i in g.edges:\n",
    "        ham += QubitOperator(f'Z{i[0]} Z{i[1]}')  # 生成哈密顿量Hc\n",
    "    return ham"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成完整的量子线路和图所对应的哈密顿量\n",
    "\n",
    "这里我们选择`p = 4`，表示选用4层的QAOA量子线路，`ansatz`是求解该问题的量子线路，`init_state_circ`是将量子态制备到均匀叠加态（$H_B$的基态）上的量子线路。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "q0: ──H────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────────────────────────‖──RX(b0)──‖──ZZ(g1)────ZZ(g1)────ZZ(g1)────────────────────────────────‖──RX(b1)──‖──ZZ(g2)────ZZ(g2)────ZZ(g2)────────────────────────────────‖──RX(b2)──‖──ZZ(g3)────ZZ(g3)────ZZ(g3)────────────────────────────────‖──RX(b3)──‖\n             │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖\nq1: ──H────ZZ(g0)──────┼─────────┼───────ZZ(g0)──────────────────────‖──RX(b0)──‖──ZZ(g1)──────┼─────────┼───────ZZ(g1)──────────────────────‖──RX(b1)──‖──ZZ(g2)──────┼─────────┼───────ZZ(g2)──────────────────────‖──RX(b2)──‖──ZZ(g3)──────┼─────────┼───────ZZ(g3)──────────────────────‖──RX(b3)──‖\n                       │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖\nq2: ──H────────────────┼───────ZZ(g0)────ZZ(g0)────ZZ(g0)────────────‖──RX(b0)──‖──────────────┼───────ZZ(g1)────ZZ(g1)────ZZ(g1)────────────‖──RX(b1)──‖──────────────┼───────ZZ(g2)────ZZ(g2)────ZZ(g2)────────────‖──RX(b2)──‖──────────────┼───────ZZ(g3)────ZZ(g3)────ZZ(g3)────────────‖──RX(b3)──‖\n                       │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖\nq3: ──H────────────────┼───────────────────────────ZZ(g0)────ZZ(g0)──‖──RX(b0)──‖──────────────┼───────────────────────────ZZ(g1)────ZZ(g1)──‖──RX(b1)──‖──────────────┼───────────────────────────ZZ(g2)────ZZ(g2)──‖──RX(b2)──‖──────────────┼───────────────────────────ZZ(g3)────ZZ(g3)──‖──RX(b3)──‖\n                       │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖\nq4: ──H──────────────ZZ(g0)──────────────────────────────────ZZ(g0)──‖──RX(b0)──‖────────────ZZ(g1)──────────────────────────────────ZZ(g1)──‖──RX(b1)──‖────────────ZZ(g2)──────────────────────────────────ZZ(g2)──‖──RX(b2)──‖────────────ZZ(g3)──────────────────────────────────ZZ(g3)──‖──RX(b3)──‖",
      "text/html": "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──H────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b0)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b1)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b2)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────────────────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b3)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">             │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖    │         │         │                                   ‖          ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──H────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)──────┼─────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)──────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b0)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)──────┼─────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)──────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b1)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)──────┼─────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)──────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b2)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)──────┼─────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)──────────────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b3)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖              │         │         │                         ‖          ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ──H────────────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b0)──‖──────────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b1)──‖──────────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b2)──‖──────────────┼───────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────────────‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b3)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖              │                             │               ‖          ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ──H────────────────┼───────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b0)──‖──────────────┼───────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b1)──‖──────────────┼───────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b2)──‖──────────────┼───────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b3)──‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                       │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖              │                                       │     ‖          ‖</span>\n<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q4: ──H──────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g0)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b0)──‖────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g1)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b1)──‖────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g2)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b2)──‖────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)──────────────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">ZZ</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(g3)──‖──</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">RX</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(b3)──‖</span>\n</pre>\n"
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "p = 4\n",
    "ham = Hamiltonian(build_ham(g))              # 生成哈密顿量\n",
    "init_state_circ = UN(H, g.nodes)             # 生成均匀叠加态，即对所有量子比特作用H门\n",
    "ansatz = build_ansatz(g, p)                  # 生成ansatz线路\n",
    "circ = init_state_circ + ansatz              # 将初始化线路与ansatz线路组合成一个线路\n",
    "circ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建待训练量子神经网络\n",
    "\n",
    "由于该问题不需要编码层量子线路，我们这里使用`MQAnsatzOnlyLayer`作为待训练的量子神经网络，并采用`Adam`优化器。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import mindspore as ms\n",
    "ms.context.set_context(mode=ms.context.PYNATIVE_MODE, device_target=\"CPU\")\n",
    "\n",
    "sim = Simulator('projectq', circ.n_qubits)                     # 创建模拟器，backend使用‘projectq’，能模拟5个比特（'circ'线路中包含的比特数）\n",
    "grad_ops = sim.get_expectation_with_grad(ham, circ)            # 获取计算变分量子线路的期望值和梯度的算子\n",
    "net = MQAnsatzOnlyLayer(grad_ops)                              # 生成待训练的神经网络\n",
    "opti = nn.Adam(net.trainable_params(), learning_rate=0.05)     # 设置针对网络中所有可训练参数、学习率为0.05的Adam优化器\n",
    "train_net = nn.TrainOneStepCell(net, opti)                     # 对神经网络进行一步训练"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 训练并展示结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true,
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stderr",
     "text": "train step: 0 , cut: [2.9995914]\ntrain step: 10 , cut: [4.337461]\ntrain step: 20 , cut: [4.6661634]\ntrain step: 30 , cut: [4.7908525]\ntrain step: 40 , cut: [4.8734603]\ntrain step: 50 , cut: [4.9015913]\ntrain step: 60 , cut: [4.9308434]\ntrain step: 70 , cut: [4.93566]\ntrain step: 80 , cut: [4.9383035]\ntrain step: 90 , cut: [4.938753]\ntrain step: 100 , cut: [4.9391074]\ntrain step: 110 , cut: [4.9392223]\ntrain step: 120 , cut: [4.9392357]\ntrain step: 130 , cut: [4.939245]\ntrain step: 140 , cut: [4.9392557]\ntrain step: 150 , cut: [4.939256]\ntrain step: 160 , cut: [4.939257]\ntrain step: 170 , cut: [4.939257]\ntrain step: 180 , cut: [4.939257]\ntrain step: 190 , cut: [4.939257]\n"
    }
   ],
   "source": [
    "for i in range(200):\n",
    "    cut = (len(g.edges) - train_net()) / 2      # 将神经网络训练一步并计算得到的结果（切割边数）。注意：每当'train_net()'运行一次，神经网络就训练了一步\n",
    "    if i%10 == 0:\n",
    "        print(\"train step:\", i, \", cut:\", cut)  # 每训练10步，打印当前训练步数和当前得到的切割边数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面的训练结果我们发现，该问题哈密顿量的基态能量对应的边切割数趋近于5。\n",
    "\n",
    "### 最优参数\n",
    "\n",
    "前面我们通过训练得到了量子线路中参数的最优值，下面，我们将最优参数提取出来并存储为字典类型，与之前线路中命名的参数一一对应。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "{'g0': 0.22442764, 'b0': -1.1389775, 'g1': 0.45309508, 'b1': -0.9446367, 'g2': 0.5337557, 'b2': -0.6775904, 'g3': 0.58395565, 'b3': -0.3823515}\n"
    }
   ],
   "source": [
    "pr = dict(zip(ansatz.params_name, net.weight.asnumpy())) # 获取线路参数\n",
    "print(pr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概率图\n",
    "\n",
    "我们将最优参数代入量子线路，通过对量子线路进行1000次采样，画出最终量子态在计算基矢下的概率分布："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "text/plain": "",
      "text/html": "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
     },
     "metadata": {}
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "shots: 1000\nKeys: q4 q3 q2 q1 q0│0.00   0.064       0.128       0.192       0.256        0.32\n────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n               00100│▒\n                    │\n               00101│▒▒\n                    │\n               01001│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01010│▒\n                    │\n               01011│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               01100│▒\n                    │\n               01101│▒\n                    │\n               10011│▒\n                    │\n               10100│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒\n                    │\n               10101│▒\n                    │\n               10110│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n                    │\n               11010│▒▒\n                    │\n               11111│▒\n                    │\n{'00100': 1, '00101': 8, '01001': 224, '01010': 1, '01011': 248, '01100': 1, '01101': 3, '10011': 2, '10100': 245, '10101': 2, '10110': 256, '11010': 7, '11111': 2}",
      "text/html": "<pre style=\"white-space: pre;\"><span style=\"color: #808000; text-decoration-color: #808000\">shots: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1000</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">Keys: q4 q3 q2 q1 q0│</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.00</span><span style=\"color: #808000; text-decoration-color: #808000\">   </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.064</span><span style=\"color: #808000; text-decoration-color: #808000\">       </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.128</span><span style=\"color: #808000; text-decoration-color: #808000\">       </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.192</span><span style=\"color: #808000; text-decoration-color: #808000\">       </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.256</span><span style=\"color: #808000; text-decoration-color: #808000\">        </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.32</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">────────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">00100</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">00101</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">01001</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">01010</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">01011</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">01100</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">01101</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">10011</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">10100</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">10101</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">10110</span><span style=\"color: #808000; text-decoration-color: #808000\">│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">11010</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">               </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">11111</span><span style=\"color: #808000; text-decoration-color: #808000\">│▒</span>\n<span style=\"color: #808000; text-decoration-color: #808000\">                    │</span>\n<span style=\"color: #808000; text-decoration-color: #808000; font-weight: bold\">{</span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;00100&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;00101&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">8</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;01001&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">224</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;01010&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;01011&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">248</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;01100&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;01101&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">3</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span>\n<span style=\"color: #008000; text-decoration-color: #008000\">&#x27;10011&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;10100&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">245</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;10101&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;10110&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">256</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;11010&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">7</span><span style=\"color: #808000; text-decoration-color: #808000\">, </span><span style=\"color: #008000; text-decoration-color: #008000\">&#x27;11111&#x27;</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #808000; text-decoration-color: #808000; font-weight: bold\">}</span>\n</pre>\n"
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "source": [
    "# pylint: disable=W0104\n",
    "circ.measure_all()                         # 为线路中所有比特添加测量门\n",
    "sim.sampling(circ, pr=pr, shots=1000)      # 运行线路1000次并打印结果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据概率分布图我们发现，该Max-Cut问题具有四个简并解，每个解对应的概率大概为25%。\n",
    "\n",
    "- `01001`：编号为1、2、4的顶点在左边，编号为0、3的顶点在右边。\n",
    "- `10110`：编号为0、3的顶点在左边，编号为1、2、4的顶点在右边。\n",
    "- `01011`：编号为2、4的顶点在左边，编号为0、1、3的顶点在右边。\n",
    "- `10100`：编号为0、1、3的顶点在左边，编号为2、4的顶点在右边。\n",
    "\n",
    "可以发现，以上结果与先前通过穷举法得到的结果相符。\n",
    "\n",
    "## 总结\n",
    "\n",
    "这里我们通过量子近似优化算法来解决了Max-Cut问题，并得到了案例中的图对应的最大切割方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "\n",
    "[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. [A Quantum Approximate Optimization Algorithm](https://arxiv.org/pdf/1411.4028.pdf)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "5545a57ef4a1ac7dca167cae0bf17fda051fcd0639773c034bd7ce77ffd97d30"
  },
  "kernelspec": {
   "display_name": "Python 3.7.5 64-bit",
   "language": "python",
   "name": "python37564bitf15e711fd06842a7ae337b5cf8b0b378"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}